# https://leetcode.cn/problems/rotated-digits/description/
# 788. 旋转数字
# medium, 刘小康 2024.09.26
# 数位DP

class Solution:
    def atMostNGivenDigitSet(self, digits: list[str], n: int) -> int:
        num = str(n)
        dp = [[0,0] for _ in range(len(num) + 1)]
        dp[0][1] = 1
        print(f"0: {dp[0]}")
        for i in range(1, len(num) + 1):
            if i > 1:
                dp[i][0] += len(digits) - 1 + dp[i - 1][0] * len(digits)
            if i == 1:
                for d in digits:
                    if d == '0':
                        continue
                    if d == num[i - 1]:
                        dp[i][1] = dp[i - 1][1]
                    elif d < num[i - 1]:
                        dp[i][0] += dp[i - 1][1]
                    else:
                        break
            else:
                for d in digits:
                    if d == num[i - 1]:
                        dp[i][1] = dp[i - 1][1]
                    elif d < num[i - 1]:
                        dp[i][0] += dp[i - 1][1]
                    else:
                        break
            print(f"{i}: {dp[i]} {num[0: i]}")
        return sum(dp[len(num)])

    def rotatedDigits(self, n: int) -> int:
        return self.atMostNGivenDigitSet(['0', '1', '2', '5', '6', '8', '9'], n) - self.atMostNGivenDigitSet(['0', '1', '8'], n)
